package pl.edu.pw.elka.dzielins.revanalyzer.utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.math3.util.ArithmeticUtils;
import org.apache.commons.math3.util.MathUtils;
import org.apache.log4j.Logger;

public class CombinatoricsUtils {
	private static final Logger LOG = Logger.getLogger(CombinatoricsUtils.class);
	
	public static String[] getCombinations(int n, int k) {
		if (k > n || k == 0)
			return null;
		if (k == n)
			return new String[] { StringUtils.rightPad("", k, "1") };
		if (k == 1) {
			String[] result = new String[n];
			for (int i = 0; i < n; ++i) {
				result[i] = StringUtils.rightPad(StringUtils.leftPad("1", i+1, "0"), n, "0");
			}
			return result;
		}
		int size = (int)(ArithmeticUtils.factorial(n)/(ArithmeticUtils.factorial(k)*ArithmeticUtils.factorial(n-k)));
		int i=0;
		String prefix = "1";
		List<String> tempList = new ArrayList<String>(size);
		while (n>=k){
			String[] subCombinations = getCombinations(--n, k-1);
			for(String subCombination:subCombinations)
				tempList.add(prefix+subCombination);
			prefix = "0"+prefix;
		}
		return tempList.toArray(new String[0]);
	}
	
	public static String[] getAllCombinations(int n) {
		if (n <= 0)
			return null;
		String[] result = null;
		for (int i = 1; i <= n; ++i)
			if (result == null)
				result = getCombinations(n, i);
			else
				result = ArrayUtils.addAll(result, getCombinations(n, i));
		return result;
	}
	
	public static <T> Set<Set<T>> getCombinations(Set<T> elements, int k) {
		if (elements == null || k > elements.size())
			return null;
		if (k == elements.size()) {
			Set<Set<T>> set = new HashSet<Set<T>>();
			set.add(elements);
			return set;
		}
		T[] array;
		array = (T[]) elements.toArray();
		Set<Set<T>> set = new HashSet<Set<T>>();
		for(String combination:getCombinations(elements.size(),k))
		{
			Set<T> subSet = new HashSet<T>();
			for(int i=0;i<combination.length();++i)
				if(combination.charAt(i)=='1')
					subSet.add(array[i]);
			set.add(subSet);
		}
		return set;
	}
	
	public static <T> Set<Set<T>> getAllCombinations(Set<T> elements) {
		if (elements == null)
			return null;
		T[] array;
		array = (T[]) elements.toArray();
		Set<Set<T>> set = new HashSet<Set<T>>();
		for(String combination:getAllCombinations(elements.size()))
		{
			Set<T> subSet = new HashSet<T>();
			for(int i=0;i<combination.length();++i)
				if(combination.charAt(i)=='1')
					subSet.add(array[i]);
			set.add(subSet);
		}
		return set;
	}
}
